package com.oocl.crm.datastructure;

import java.util.Comparator;

import com.oocl.crm.exception.CrmException;

/*
 * Construct a two-way linked list storing integers.
 */
public class MyLinkedList<T extends HasId> {

	private int size;

	class Node<E> {
		E element;
		Node<E> prev;
		Node<E> next;

		Node(E element, Node<E> prev, Node<E> next) {
			this.element = element;
			this.prev = prev;
			this.next = next;
		}
	}

	private Node<T> head;
	private Node<T> tail;

	public MyLinkedList() {
		size = 0;
	}

	/*
	 * Insert an element at the specified location
	 */
	public void insert(int index, T element) throws CrmException {
		// Negative index is not valid
		if (index < 0) {
			throw new CrmException("Out of index!");
		}

		// If the list is empty, insert the first node
		if (head == null) {
			if (index != 0) {
				throw new CrmException("Out of index!");
			}

			Node<T> firstNode = new Node<T>(element, null, null);
			head = firstNode;
			tail = firstNode;
			size++;
			return;
		}

		// Find the location to insert
		Node<T> pointer = head;
		int counter = 0;
		for (; counter < index && pointer != null; counter++, pointer = pointer.next)
			;
		if (counter < index) {
			throw new CrmException("Out of index!");
		}

		// If the pointer has reached after the tail, insert the element at tail
		if (pointer == null) {
			Node<T> newPtr = new Node<T>(element, tail, pointer);
			tail.next = newPtr;
			tail = newPtr;
			size++;
			return;
		}

		// Construct a new node
		Node<T> prevPtr = pointer.prev;
		Node<T> newPtr = new Node<T>(element, prevPtr, pointer);

		// If last pointer is null, then new element will replace the head
		// pointer
		if (prevPtr == null) {
			head.prev = newPtr;
			head = newPtr;
		} else {
			prevPtr.next = newPtr;
			pointer.prev = newPtr;
		}
		size++;
	}

	/*
	 * copy a list
	 */
	@Override
	public MyLinkedList<T> clone() {
		MyLinkedList<T> newList = new MyLinkedList<>();
		try {
			for (Node<T> pointer = head; pointer != null; pointer = pointer.next) {
				newList.insert(newList.getSize(), pointer.element);
			}
		} catch (CrmException e) {
			e.printStackTrace();
		}
		return newList;
	}

	/*
	 * Find by id
	 */
	public T findById(String id) throws CrmException {
		// If the list is empty, do nothing
		if (head == null) {
			throw new CrmException("List is empty!");
		}

		// Find element by id
		Node<T> pointer = head;
		for (; pointer != null && !id.equals(pointer.element.getId()); pointer = pointer.next)
			;
		if (pointer == null) {
			throw new CrmException("Customer with such id not found!");
		}

		return pointer.element;
	}

	/*
	 * Update element info
	 */
	public void updateById(T newElement) throws CrmException {
		// If the list is empty, do nothing
		if (head == null) {
			throw new CrmException("List is empty!");
		}

		// Find element by id
		Node<T> pointer = head;
		for (; pointer != null
				&& !newElement.getId().equals(pointer.element.getId()); pointer = pointer.next)
			;
		if (pointer == null) {
			throw new CrmException("Customer with such id not found!");
		}

		// Replace with new element
		pointer.element = newElement;
	}

	/*
	 * Remove a element with specified id
	 */
	public void removeById(String id) throws CrmException {
		// If the list is empty, do nothing
		if (head == null) {
			return;
		}

		// Find the location to remove
		Node<T> pointer = head;
		for (; pointer != null && !id.equals(pointer.element.getId()); pointer = pointer.next)
			;
		if (pointer == null) {
			throw new CrmException("Customer with such id not found!");
		}

		// When removing the head
		if (pointer == head) {
			Node<T> nextPtr = head.next;
			
			// When removing the only element
			if (nextPtr == null) {
				head = tail = null;
				size = 0;
				return;
			}
			
			nextPtr.prev = null;
			head = nextPtr;
			size--;
			return;
		}

		// When removing the tail
		if (pointer == tail) {
			Node<T> prevPtr = tail.prev;
			
			// When removing the only element
			if (prevPtr == null) {
				head = tail = null;
				size = 0;
				return;
			}
						
			prevPtr.next = null;
			tail = prevPtr;
			size--;
			return;
		}

		// other situations
		Node<T> prevPtr = pointer.prev;
		Node<T> nextPtr = pointer.next;
		prevPtr.next = nextPtr;
		nextPtr.prev = prevPtr;
		size--;
	}

	/*
	 * sort by condition (ascending)
	 */
	public MyLinkedList<T> sortBy(Comparator<T> comparator) {
		MyLinkedList<T> sortedList = this.clone();

		// Begin sorting
		for (int s = size; s > 1; s--) {
			for (Node<T> pointer = sortedList.head; pointer.next != null; pointer = pointer.next) {
				if (comparator.compare(pointer.element, pointer.next.element) > 0) {
					T temp = pointer.element;
					pointer.element = pointer.next.element;
					pointer.next.element = temp;
				}
			}
		}

		return sortedList;
	}

	/*
	 * Find element at specified index
	 */
	public T elementAt(int index) throws CrmException {
		int counter = 0;
		for (Node<T> pointer = head; pointer != null; pointer = pointer.next, counter++) {
			if (counter == index) {
				return pointer.element;
			}
		}
		throw new CrmException("Out of index!");
	}

	/*
	 * Get size of list
	 */
	public int getSize() {
		return size;
	}
	
	/*
	 * Clear the list
	 */
	public void clear() {
		while (size > 0) {
			Node<T> nextPtr = head.next;
			
			// When removing the only element
			if (nextPtr == null) {
				head = tail = null;
				size = 0;
				return;
			}
						
			nextPtr.prev = null;
			head = nextPtr;
			size--;
		}
	}

	/*
	 * Print the list
	 */
	public String getListAsString() {
		if (head == null) {
			return "null";
		}

		String result = "";
		for (Node<T> pointer = head; pointer != null; pointer = pointer.next) {
			result += pointer.element.toString() + "\n";
		}

		return result;
	}

}
